The present invention relates generally to the art of representing shapes of objects and models, and more particularly to computer implemented methods for operating on the represented shapes.
Rivaling polygons, distance fields are well known as fundamental primitive for representing objects and models in computer graphics, see for example, U.S. Pat. No. 6,040,835 issued to Gibson on Mar. 21, 2000, and U.S. Pat. No. 6,084,593 issued to Gibson on Jul. 4, 2000.
In the prior art, a distance field is usually described with the notion that every point in space is associated with a xe2x80x9cminimumxe2x80x9d distance to a surface on the object or model. This notion derives both from natural experience and the classic definition in mathematics in which a distance from a point y in a metric space to a set A is given by the infimum
D(y,A)=infxxcex5AD(x,y),
where D(x,y) is a standard metric such as the Manhattan distance, i.e. the sum of absolute differences of components, the Euclidean distance, i.e., the square root of the sum of the squares of the components, or the infinity norm, i.e. the maximum of the absolute differences of the components; known respectively as the l1, l2 and l∞ norms.
Whatever the metric, a traditional distance field requires searching for a point on a surface of the object or model that is closest to a point in space, i.e., a point in the distance field. For example, the distance field can be determined by an intensive method that finds a nearest point on the surface to any given point in space by casting sample rays from the point in space, and then using Newton""s approximation method to converge on the point on the surface. This search can be time-consuming and complicated. Furthermore, the search can be subject to many optimization pitfalls.
Unfortunately, the traditional notion of the minimum distance also excludes many useful shapes. Implicitly defined shapes, for example, do not reference a minimum distance, nor do they necessarily designate a closest point on a surface of the object to allow one to completely define the distance field.
For example, with an implicit function f(x)=20x2+y2+z2xe2x88x921, any point x in three-dimensional space f(x) represents a very usable distance to the flattened ellipsoid defined by f(x)=0, an algebraic, i.e., non-Euclidean, distance that has no minimum or closest point in the calculation. Level sets, interpolation schemes, measured equipotential fields and procedural methods are other examples for which distance fields either fail to represent, or impose unnecessary computational burdens on the representation. In addition, repeated operations on distance field can degrade quality of the field, making further operations inaccurate, unpredictable, or worse, impossible to perform.
For example, FIG. 1a shows contracting streamlines 101 of a cubic implicial test function on a test surface 102, and FIG. 1b expansion and twist of streamlines 103 on the test surface 104. There are eight streamlines emanating from the four corners and four midpoints of the depicted square 105. In FIG. 1a, the streamlines 101 contract as they flow to the surface in a region of concavity. In FIG. 1b, the streamlines 102 expand to meet a region of convexity 102. The streamlines in FIG. 1a also exhibit some twist to the flux, especially where the horizontal beginning points on the square project 105, with a turn, onto the convex surface. It would be desirable to minimize the contraction, expansion and rotation of the streamlines.
FIG. 2a shows a more tortuous path of streamlines 201 when the object or model has a small amount of texture. FIG. 2b shows a complete failure in the streamlines due to a lager amount of texture. This is due to the fact that the distance field has a large number of local minima that trap the streamlines.
It is desired to regularize a field surrounding shapes of objects and models so that repeated operation such Booleans, blending and texturing can be applied without deleterious effects on the field.
The invention provides a method for regularizing a distance field of a graphics model or object. The distance field includes variable scalar values and a set of fixed zero values. The zero values define a boundary or surface of the object.
The distance field is evaluated by a cost function, optimized according predetermined parameters, to determine a cost of the distance field. The variable scalar values are then randomly perturbed while holding the zero values fixed. The evaluating, determining, perturbing steps are repeated until the cost is less than a predetermined threshold.
The distance field can be in the form of a non-differentiable implicial field. A surface of the graphics model can be textured or stenciled by following streamlines along the gradients of the regularized distance field.